/************************************************************************

								Heroes IV
					  Copyright 2000, The 3DO Company

	------------------------------------------------------------------
  						       army.cpp

	$Header: /game/army.cpp $

	$NoKeywords: $

 ************************************************************************/

// kill the 255+ character identifier warning.  Templates tend to exceed that easily.
#include "precompiled.h"
#pragma warning( disable: 4786 )

#include "army.h"

#include <algorithm>
#include <assert.h>

#include "abstract_script_action.h"
#include "adv_actor_model.h"
#include "adv_actor_model_cache.h"
#include "adv_object_icon_type.h"
#include "adventure_ai.h"
#include "adventure_enemy_marker.h"
#include "adventure_frame.h"
#include "adventure_map.h"
#include "adventure_map_window.h"
#include "ai_army_data_cache.h"
#include "ai_importance.h"
#include "ai_value.h"
#include "alignment_relationship.h"
#include "angle.h"
#include "army_dialog.h"
#include "army_info_window.h"
#include "army_list.h"
#include "army_mover.h"
#include "combat_context_army.h"
#include "combat_context_ptr.h"
#include "combat_result.h"
#include "creature.h"
#include "creature_ability.h"
#include "creature_traits.h"
#include "dialog_charm.h"
#include "dialog_enemy_runs.h"
#include "dialog_full_army.h"
#include "direction.h"
#include "elements_of.h"
#include "enum_operations.h"
#include "external_string.h"
#include "float_object.h"
#include "hero.h"
#include "hero_class_properties.h"
#include "map_point.h"
#include "music.h"
#include "options.h"
#include "ownable_event.h"
#include "path_search_type.h"
#include "platform.h"
#include "player.h"
#include "player_color.h"
#include "random.h"
#include "respawn_point.h"
#include "run_combat.h"
#include "script_targeting.h"
#include "simple_dialog.h"
#include "sized_int_types.h"
#include "spell.h"
#include "streambuf_operators.h"
#include "terrain.h"
#include "town_building.h"
#include "town_type.h"
#include "triggerable_event.h"

extern t_external_string const k_text_empty_ship_name( "empty_ship_name.misc" );

// ---------------------------------------------------------------
// unnamed namespace
// ---------------------------------------------------------------

namespace
{

	int const k_current_map_format_version = 9;
	int const k_current_save_format_version = 9;

	// ------------------------------------------------------------
	// ------------------------------------------------------------
	template < typename t_event_list >
	bool read_events_from_map(
		std::streambuf &	stream,
		int					version,
		t_event_list &		events )
	{
		typedef typename t_event_list::value_type	t_event_ptr;
		typedef typename t_event_ptr::element_type	t_event;

		int count = get< t_uint16 >( stream );

		t_event_list new_events;
		new_events.reserve( count );

		while ( count > 0 )
		{
			t_event_ptr new_event_ptr( new t_event );
			if ( !new_event_ptr->read_from_map( stream ) )
				return false;

			new_events.push_back( new_event_ptr );

			--count;
		}

		events.swap( new_events );

		return true;
	}

	// ------------------------------------------------------------
	// ------------------------------------------------------------
	template < typename t_event_list >
	bool read_events(
		std::streambuf &	stream,
		int					version,
		int					script_version,
		t_event_list &		events )
	{
		assert( version >= 4 );

		typedef typename t_event_list::value_type	t_event_ptr;
		typedef typename t_event_ptr::element_type	t_event;

		int count = get< t_uint16 >( stream );

		t_event_list new_events;
		new_events.reserve( count );

		while ( count > 0 )
		{
			t_event_ptr new_event_ptr( new t_event );
			if ( !new_event_ptr->read( stream, script_version ) )
				return false;

			new_events.push_back( new_event_ptr );

			--count;
		}

		events.swap( new_events );

		return true;
	}

	// ------------------------------------------------------------
	// ------------------------------------------------------------
	template < typename t_event_list >
	bool write_events(
		std::streambuf &		stream,
		t_event_list const &	events )
	{
		put< t_uint16 >( stream, events.size() );

		typedef typename t_event_list::const_iterator t_event_iter;
		t_event_iter event_end = events.end();
		t_event_iter event_iter = events.begin();
		for ( ; event_iter != event_end; ++event_iter )
		{
			if ( !( *event_iter )->write( stream ) )
				return false;
		}

		return true;
	}

	// ------------------------------------------------------------
	// footprint information for graveyard
	// ------------------------------------------------------------
	class t_graveyard_footprint : public t_footprint
	{
		virtual bool           are_any_cells_flat() const;
		virtual bool           are_any_cells_impassable() const;
		virtual t_map_point_2d get_size() const;
		virtual bool           is_cell_flat( t_map_point_2d const & point ) const;
		virtual bool           is_cell_impassable( t_map_point_2d const & point ) const;
		virtual bool           is_left_edge_trigger( t_map_point_2d const & point ) const;
		virtual bool           is_right_edge_trigger( t_map_point_2d const & point ) const;
		virtual bool           is_trigger_cell( t_map_point_2d const& point ) const;
	};

} // unnamed namespace

// ---------------------------------------------------------------
// army which appears on the adventure map
// ---------------------------------------------------------------
t_army::t_army()
{
	init();
};

// ---------------------------------------------------------------
// army which appears on the adventure map
// ---------------------------------------------------------------
t_army::t_army( t_creature_array* creatures )
      : t_creature_array( creatures ) 
{
	init();
}

t_army::t_army( t_army* army )
      : t_creature_array( army )
{
	init();
	m_owner		= army->get_owner_number();
	m_boat_type	= army->get_boat_type();
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// ---------------------------------------------------------------
t_army::t_army( t_town_type boat_type )
{
	init();
	m_boat_type = boat_type;
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// Constructor for respawns
// ---------------------------------------------------------------
t_army::t_army( t_creature_type					creature_type,
				int								creature_count,
				int								initial_growing_experience_value,
				int								initial_max_growth_per_day,
				int								initial_non_growing_experience_value,
				t_patrol_type					patrol_type,
				t_uint8							patrol_radius,
				t_adv_map_point					initial_location )
{
	init();

	m_initial_alignment = get_traits( creature_type ).alignment;
	m_initial_growing_experience_value = initial_growing_experience_value;
	m_initial_max_growth_per_day = initial_max_growth_per_day;
	m_initial_non_growing_experience_value = initial_non_growing_experience_value;
	m_patrol_type = patrol_type;
	m_patrol_radius = patrol_radius;
	m_initial_location = initial_location;


	// Only pirates, water elementals, sea monsters, and mermaids 
	// respawn on water. Of those, only pirates need a boat. Pirates
	// never respawn on land.
	if ( creature_type == k_pirate )
		m_boat_type = k_town_chaos;

	t_creature_array::add( creature_type, creature_count );
}


// ---------------------------------------------------------------
// army which appears on the adventure map
// ---------------------------------------------------------------
void t_army::init()
{
	m_model_ptr = get_adv_actor_model_cache( "hero.chaos_magic_female" ).get();

	assert( m_model_ptr.get() != 0 );

	set_action( k_adv_actor_action_wait );

	m_in_combat = false;
	m_initial_alignment = k_town_none;
	m_initial_growing_experience_value = -1;
	m_initial_max_growth_per_day = -1;
	m_initial_non_growing_experience_value = -1;
	m_is_graveyard = false;
	m_path_destination.row = -1;
	m_path_destination.column = -1;
	m_path_destination.level = -1;
	m_path_destination.on_bridge = false;
	m_path_start_cost = 0;
	m_owner = -1;
	m_boat_type = k_town_none;
	m_player_color = k_player_gray;
	m_on_owner_army_list = false;
	m_on_owner_graveyard_list = false;
	m_on_owner_object_list = false;
	m_scouting_range = 0;
	m_ai_wander_direction = -1;
	m_ai_importance = k_ai_importance_normal;
	m_sleeping = false;
	m_add_starting_troops = false;

	std::fill(
		m_built_in_events,
		m_built_in_events + k_built_in_event_count,
		t_built_in_event_ptr( new t_built_in_event ) );
}


// ---------------------------------------------------------------
// army which appears on the adventure map
// ---------------------------------------------------------------
t_army::~t_army()
{
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// place on owner's army list
// ---------------------------------------------------------------
void t_army::add_to_owner_army_list()
{
	assert( !m_is_graveyard );

	t_player* owner = get_owner();

	if (owner == 0)
		return;

	if (!m_on_owner_army_list && !empty())
	{
		m_on_owner_army_list = true;
		owner->add_army( this );
	}
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// place on owner's graveyard list
// ---------------------------------------------------------------
void t_army::add_to_owner_graveyard_list()
{
	assert( m_is_graveyard );

	t_player* owner = get_owner();

	if (owner == 0)
		return;

	if (!m_on_owner_graveyard_list && !empty())
	{
		m_on_owner_graveyard_list = true;
		owner->add_graveyard( this );
	}
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// place on owner's object list
// ---------------------------------------------------------------
void t_army::add_to_owner_object_list()
{
	t_player* owner = get_owner();

	if (owner == 0)
		return;

	if (!m_on_owner_object_list)
	{
		m_on_owner_object_list = true;
		owner->add_object( this );
	}
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// remove from owner's army list
// ---------------------------------------------------------------
void t_army::remove_from_owner_army_list()
{
	if (m_on_owner_army_list)
	{
		m_on_owner_army_list = false;
		t_player* owner = get_owner();
		if (owner != 0)
			owner->remove_army( this );
	}
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// remove from owner's graveyard list
// ---------------------------------------------------------------
void t_army::remove_from_owner_graveyard_list()
{
	if (m_on_owner_graveyard_list)
	{
		m_on_owner_graveyard_list = false;
		t_player* owner = get_owner();
		if (owner != 0)
			owner->remove_graveyard( this );
	}
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// remove from owner's object list
// ---------------------------------------------------------------
void t_army::remove_from_owner_object_list()
{
	if (m_on_owner_object_list)
	{
		m_on_owner_object_list = false;
		t_player* owner = get_owner();
		if (owner != 0)
			owner->remove_object( this );
	}
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// place on all owner's applicable lists
// ---------------------------------------------------------------
void t_army::add_to_owner_lists()
{
	add_to_owner_object_list();
	if ( m_is_graveyard )
		add_to_owner_graveyard_list();
	else
		add_to_owner_army_list();
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// remove from all owner's lists
// ---------------------------------------------------------------
void t_army::remove_from_owner_lists()
{
	remove_from_owner_graveyard_list();
	remove_from_owner_army_list();
	remove_from_owner_object_list();
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// ---------------------------------------------------------------
void t_army::update_state()
{
	t_actor::update_state();

	m_is_graveyard	= true;
	bool is_empty	= true;
	for (int i = 0; i < t_creature_array::k_size; i++)
	{
		if (m_data[i]->get_number() > 0)
		{
			is_empty = false;
			if (!m_data[i]->is_dead())
			{
				m_is_graveyard = false;
				break;
			}
		}
	}

	t_model_ptr new_model;

	bool highlight = false;
	if (is_empty) 
	{
		m_is_graveyard = false;

		if (is_boat())
		{
			// Empty boats don't count as armies or graveyards, but they are still owned objects
			remove_from_owner_graveyard_list();
			remove_from_owner_army_list();

			std::string model_name = "ships.";
			model_name += k_town_keyword[ m_boat_type ];
			new_model = get_adv_actor_model_cache( model_name ).get();
		}
		else
		{
			remove_from_owner_lists();

			// Leave empty land armies alone since they're going away soon anyway
			return;
		}
	}
	else
	{
		t_creature_stack const& leader = get_leader();

		if (m_is_graveyard)
		{
			remove_from_owner_army_list();
			add_to_owner_graveyard_list();

			m_boat_type = k_town_none;	// If we're a graveyard, we're not a boat anymore

			std::string model_name = "tombstones.";
			model_name += k_town_keyword[ leader.get_alignment() ];
			new_model = get_adv_actor_model_cache( model_name ).get();
		} 
		else 
		{
			remove_from_owner_graveyard_list();
			add_to_owner_army_list();

			t_creature const* creature = leader.get_creature();
			if (is_boat())
			{
				std::string model_name = "ships.";
				model_name += k_town_keyword[ m_boat_type ];
				new_model = get_adv_actor_model_cache( model_name ).get();
			}
			else if (creature != 0)
			{
				new_model = get_adv_model( creature->get_creature_type() );
			}
			else
			{
				t_hero const* hero = leader.get_hero();
				new_model = get_adv_model( hero->get_alignment(), hero->is_male(), 
					hero->uses_spellcaster_model() );
			}

			highlight = get_owner_number() < 0;
		}
	}

	update_scouting_range();

	if ( new_model.get() == m_model_ptr.get() && highlight == is_highlighted() )
		return;

	t_float_object floater( this );

	if ( new_model.get() != m_model_ptr.get() )
	{
		m_model_ptr = new_model;
		on_model_changed();
	}

	enable_highlight( highlight );
	
	if (m_map!=NULL)
		m_map->record_update_event( this );
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// ---------------------------------------------------------------
void t_army::process_new_day()
{
	t_creature_array::process_new_day( true );
	t_actor::process_new_day();
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// ---------------------------------------------------------------
t_army* t_army::get_army()
{
	return this;
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// ---------------------------------------------------------------
t_army const* t_army::get_army() const
{
	return this;
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// ---------------------------------------------------------------
t_army::t_model const & t_army::get_model() const
{
	return *m_model_ptr;
}

// ---------------------------------------------------------------
// Show army info.
// ---------------------------------------------------------------
void t_army::right_click( t_mouse_event const& event,
		                  t_adventure_frame* adventure_frame )
{
	t_army_ptr ref = this;

	run_army_info_window( this, adventure_frame );

	// if this army is owned by local player, select it as well
	if( adventure_frame )
	{
		t_adventure_map* map = adventure_frame->get_map();
		if(    map 
			&& get_owner_number() == map->get_player_number() 
			&& is_on_map() 
			&& !empty()
			&& !is_graveyard() )
		{
			adventure_frame->select_army( this );
		}
	}
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// ---------------------------------------------------------------
std::string	t_army::get_name() const
{
	if ( empty() && is_boat() )
		return k_text_empty_ship_name;

	t_creature_stack const& leader = get_leader();
	return leader.get_army_name();
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// set new path
// ---------------------------------------------------------------
void t_army::set_path( t_adventure_path const& path )
{
	m_path = path;
	m_path_start_cost = 0;
	if (path.empty())
	{
		m_path_destination.row = -1;
		m_path_destination.column = -1;
	}
	else
		m_path_destination = path.front();
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// get the correct cursor
// ---------------------------------------------------------------
t_bitmap_cursor const& t_army::get_cursor( t_adventure_map_window const& window,
		                                   t_army const* army ) const
{
	if (army == 0)
		return window.get_normal_cursor();
	if (same_team( army->get_owner(), get_owner() ) )
		return window.get_transfer_cursor();
	if (empty() && m_boat_type != k_town_none)
		return window.get_activate_cursor();
	if (m_is_graveyard)
		return window.get_move_cursor();
	return window.get_attack_cursor();
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// ---------------------------------------------------------------
void t_army::move( t_level_map_point_2d const& point )
{
	t_adv_map_point			new_point( point, m_location.on_bridge );
	t_adventure_tile const& tile = m_map->get_adv_tile( point );

	new_point.on_bridge = tile.has_ramp() || (m_location.on_bridge && tile.has_bridge());
	t_actor::move( new_point );
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// leave boat and enter new square
// ---------------------------------------------------------------
void t_army::leave_boat( t_level_map_point_2d const& point )
{
	// Create a new empty boat in our place
	t_army_ptr boat;
	boat = new t_army( m_boat_type );
	boat->set_owner( get_owner_number() );
	boat->place( *m_map, get_position() );

	// Morph ourselves into a land army
	m_boat_type = k_town_none;
	move( point );
	m_path_destination.row = -1;
	m_path_destination.column = -1;
	expend_embarkation_movement();

	// Update things
	update_state();
	t_adventure_frame* frame = get_adventure_frame();
	frame->update();
	frame->refresh_path();
	frame->reset_pathfinder();
	update_frame();
}

// ---------------------------------------------------------------
// Is this army a graveyard? Override for 
// t_creature_array::is_graveyard
// ---------------------------------------------------------------
bool t_army::is_graveyard() const
{
	return m_is_graveyard;
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// get charmed creatures
// ---------------------------------------------------------------
static void get_charmed_creatures( t_creature_array&		charm_creatures,
								   t_creature_array const&	total_creatures,
								   int						percentage,
								   t_hero const&			hero )
{
	t_creature const*	creature;
	int					amount;
	int					i;
	int					experience;
	int					experience_limit;
	static int const    k_limit[] = { 60, 60, 120, 180, 240, 300 };
	int					limit;

	assert( percentage >= 0 && percentage <= 100 );

	const int offset = hero.get_skill( k_skill_charm ) + 1;
	assert( offset < sizeof(k_limit)/sizeof(k_limit[0]) );
	limit = k_limit[ offset ];
	limit += limit * (hero.get_level() - 1) / 10;

	for (i = 0; i < t_creature_array::k_size; ++i)
	{
		creature = total_creatures[i].get_creature();

		// charm does not affect heroes
		if (creature == 0)
			continue;

		// charm does not affect undead and mechanical creatures
		if (creature->has_ability( k_ability_undead )
			|| creature->has_ability( k_ability_mechanical ))
			continue;

		// the mermaid and the sea monster, cost zero, cannot be recruited.
		if (creature->get_creature_type() == k_mermaid 
			|| creature->get_creature_type() == k_sea_monster)
			continue;

		// Decide how many creature we may potentially recruite
		amount = creature->get_number() * percentage / 100;
		if (amount == 0)
			continue;

		// Decide how many of the creature we can affort to recruite
		experience = creature->get_experience_value( 1 );
		experience_limit = limit / experience;
		if (experience_limit < amount)
			amount = experience_limit;
		if (amount == 0)
			continue;

		// Recruite the creatures
		limit -= experience * amount;
		charm_creatures.add( creature->get_creature_type(), amount );
	}
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// get creatures swayed by diplomacy
// ---------------------------------------------------------------
static void get_diplomacy_creatures( t_creature_array&			diplomacy_creatures,
									 t_creature_array const&	total_creatures,
									 t_creature_array const&	our_creatures,
									 int						percentage,
									 t_hero const&				hero )
{
	bool				allowed_alignments[k_town_type_count];
	t_town_type			alignment;
	t_town_type			town;
	t_creature const*	creature;
	int					amount;
	int					i;
	static int const    k_limit[] = { 120, 120, 240, 360, 480, 600 };
	int					limit;

	assert( percentage >= 0 && percentage <= 100 );

	const int offset = hero.get_skill( k_skill_diplomacy ) + 1;
	assert( offset < sizeof(k_limit)/sizeof(k_limit[0]) );
	limit = k_limit[ offset ];
	limit += limit * (hero.get_level() - 1) / 10;

	// can't use diplomacy on any creatures that are opposed to
	// existing creatures
	for (i = 0; i < k_town_type_count; ++i)
		allowed_alignments[i] = true;
	for (i = 0; i < t_creature_array::k_size; ++i)
	{
		if (our_creatures[i].get_number() == 0)
			continue;
		alignment = our_creatures[i].get_alignment();
		for (town = t_town_type(0); town < k_town_type_count; enum_incr( town ))
		{
			if (get_alignment_relationship( alignment, town ) == k_alignments_hostile)
				allowed_alignments[town] = false;
		}
	}

	int experience;
	int experience_limit;

	for (i = 0; i < t_creature_array::k_size; ++i)
	{
		creature = total_creatures[i].get_creature();

		// diplomacy does not affect heroes
		if (creature == 0)
			continue;

		// don't bother with "opposed" creatures 
		if (!allowed_alignments[creature->get_alignment()])
			continue;

		// the mermaid and the sea monster, cost zero, cannot be recruited.
		if (creature->get_creature_type() == k_mermaid 
			|| creature->get_creature_type() == k_sea_monster)
			continue;

		// Decide how many creature we may potentially recruite
		amount = creature->get_number() * percentage / 100;
		if (amount == 0)
			continue;

		// Decide how many of the creature we can affort to recruite
		experience = creature->get_experience_value( 1 );
		experience_limit = limit / experience;
		if (experience_limit < amount)
			amount = experience_limit;
		if (amount == 0)
			continue;

		// Recruite the creatures
		limit -= experience * amount;
		diplomacy_creatures.add( creature->get_creature_type(), amount );
	}
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// merge two armies, if possible
// ---------------------------------------------------------------
void merge( t_creature_array& destination, t_creature_array& source )
{
	int i;

	for (i = 0; i < t_creature_array::k_size; ++i)
	{
		if (source[i].get_number() == 0)
			continue;
		if (destination.add( source[i].get_creature_type(), source[i].get_number() ))
			source.clear( i );
	}
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// remove creatures from an army
// ---------------------------------------------------------------
static void remove( t_creature_array& army, t_creature_array const& removed )
{
	int				i;
	int				j;
	int				amount;
	t_creature_type creature_type;

	for (i = 0; i < t_creature_array::k_size; ++i)
	{
		amount = removed[i].get_number();
		if (amount == 0)
			continue;
		creature_type = removed[i].get_creature_type();
		for (j = 0; j < t_creature_array::k_size; ++j)
		{
			if (army[j].get_creature_type() == creature_type)
			{
				if (amount <= army[j].get_number())
				{
					army.remove( amount, j );
					break;
				}
				amount -= army[j].get_number();
				army.clear( j );
			}
		}
	}
}

inline int get_skill_power( t_hero const* hero, t_skill_type skill )
{
	if (hero == 0)
		return 0;
	return hero->get_skill_power( skill );
}

inline t_skill_mastery get_charm_skill_level( t_hero const* hero, t_skill_type skill )
{
	if (hero == 0)
		return k_mastery_basic;
	if (hero->get_skill( skill ) < k_mastery_basic)
		return k_mastery_basic;
	return hero->get_skill( skill );
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// handle any charm / diplomacy interactions between armies
// ---------------------------------------------------------------
void t_army::do_charm( t_army* army, t_adventure_frame* frame )
{
	t_player* enemy_player = army->get_owner();

	if (enemy_player == 0) 
		return;

	t_creature_array&	enemy_creatures = army->get_creatures();
	int					enemy_power = enemy_creatures.get_experience_value();
	int					power = get_experience_value();

	// only allow diplomacy / charm if we're outnumbered 3:1 or more
	if (enemy_power < 3 * power)
		return;

	t_hero*			 attacking_charmer;
	t_hero*			 attacking_diplomat;
	int				 attacking_charm;
	int				 attacking_diplomacy;
	int				 defending_charm;
	int				 defending_power;
	t_creature_array candidate_creatures;
	t_ai_army		 charm_creatures( army->get_map(), get_owner() );
	t_ai_army		 diplomacy_creatures( army->get_map(), get_owner() );
	int				 i;

	for (i = 0; i < t_creature_array::k_size; ++i)
	{
		if ((*this)[i].get_number() != 0 && (*this)[i].get_creature() != 0)
			candidate_creatures.add( (*this)[i].get_creature_type(), (*this)[i].get_number() );
	}
	attacking_charmer = enemy_creatures.get_most_powerful_skill( k_skill_charm );
	attacking_charm = get_skill_power( attacking_charmer, k_skill_charm );
	attacking_diplomat = enemy_creatures.get_most_powerful_skill( k_skill_diplomacy );
	attacking_diplomacy = get_skill_power( attacking_diplomat, k_skill_diplomacy );
	defending_charm = get_most_powerful_skill_power( k_skill_charm );
	defending_power = get_most_powerful_skill_power( k_skill_diplomacy );
	if (defending_power < defending_charm * 2)
		defending_power = defending_charm * 2;

	// Apply charm first
	if (attacking_charm > defending_power / 2)
	{
		get_charmed_creatures( charm_creatures, candidate_creatures, 
							   attacking_charm - defending_power / 2,
							   *attacking_charmer );
	}

	// Apply diplomacy to the remainder of the (uncharmed) creatures
	if (attacking_diplomacy > defending_power)
	{
		get_diplomacy_creatures( diplomacy_creatures, candidate_creatures, *army, 
			                     attacking_diplomacy - defending_power,
								 *attacking_diplomat );
	}

	// If we didn't get anywhere, bail out
	if (charm_creatures.empty() && diplomacy_creatures.empty())
		return;

	if (enemy_player->is_computer())
	{
		float	diplomacy_value = 0.0;
		float	charm_value = 0.0;
		int		diplomacy_cost = 0;
		t_ai_army_builder diplomacy_builder( *army->get_ai(), army->get_creatures(), diplomacy_creatures );
		t_ai_army_builder charm_builder( *army->get_ai(), army->get_creatures(), charm_creatures );

		if (!diplomacy_creatures.empty())
		{
			for (i = 0; i < t_creature_array::k_size; ++i)
			{
				if (diplomacy_creatures[i].get_number() == 0)
					continue;
				diplomacy_cost += diplomacy_creatures[i].get_creature()->get_traits().cost[k_gold]
								  *	diplomacy_creatures[i].get_number();
			}
			diplomacy_cost >>= 1;
			
			if (enemy_player->ai_get_discretionary_amount(k_gold) > diplomacy_cost)
			{
				float value_of_xp = ai_value_of_xp( army, diplomacy_creatures.get_experience_value());

				float value_of_merge = diplomacy_builder.shuffle_armies();
				float cost_value = diplomacy_cost * enemy_player->get_material_value( k_gold );

				diplomacy_value = value_of_merge - cost_value - value_of_xp;
			}
		}

		if (!charm_creatures.empty())
		{
			float value_of_xp = ai_value_of_xp( army, charm_creatures.get_experience_value());

			float value_of_merge = charm_builder.shuffle_armies();

			charm_value = value_of_merge - value_of_xp;
		}

		if (charm_value <= 0.0 && diplomacy_value <= 0.0)
			return;

		if (diplomacy_value > charm_value)
		{
			::remove( *this, diplomacy_creatures );
			t_material_array actual_cost;
			actual_cost[k_gold] = diplomacy_cost;
			enemy_player->ai_spend_discretionary( actual_cost );
			diplomacy_builder.build_armies( army->get_creatures(), diplomacy_creatures);
			charm_creatures.clear();
		}
		else
		{
			::remove( *this, charm_creatures );
			charm_builder.build_armies( army->get_creatures(), charm_creatures );
		}
		// place any leftovers
		if (!charm_creatures.empty())
			create_army( *army, charm_creatures );
		return;
	}

	// create the results/choice window
	t_counted_ptr<t_dialog_charm>	dialog;
	int								result;
	t_skill_mastery					enemy_diplomacy;
	t_skill_mastery					enemy_charm;

	enemy_charm		= get_charm_skill_level( attacking_charmer, k_skill_charm );
	enemy_diplomacy = get_charm_skill_level( attacking_diplomat, k_skill_diplomacy );
	dialog = new t_dialog_charm( diplomacy_creatures, charm_creatures, enemy_diplomacy,
								 enemy_charm, enemy_player->get_funds()[k_gold], frame );
	result = dialog->run_modal();

	// Apply the users choices
	switch (result)
	{
		case t_dialog_charm::k_result_cancel:
			return;

		case t_dialog_charm::k_result_charm:
			::remove( *this, charm_creatures );
			merge( enemy_creatures, charm_creatures );
			break;

		case t_dialog_charm::k_result_diplomacy:
			enemy_player->spend( k_gold, dialog->get_diplomacy_cost() );
			::remove( *this, diplomacy_creatures );
			merge( enemy_creatures, diplomacy_creatures );
			charm_creatures.clear();
			merge( charm_creatures, diplomacy_creatures );
			break;
	}

	// If we couldn't place all the recruited creatures automaticly, display the army dialog
	if ( !charm_creatures.empty() )
	{
		t_counted_ptr<t_dialog_full_army> dialog_ptr;

		dialog_ptr = new t_dialog_full_army( frame );
		dialog_ptr->init_dialog( enemy_creatures, charm_creatures );
		dialog_ptr->run_modal();
	}
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// handle interaction between armies
// ---------------------------------------------------------------
void t_army::activate_trigger( t_army* army, t_adv_map_point const& point, 
							   t_direction direction, 
							   t_adventure_frame* frame )
{
	touch_armies( army, point, direction, frame, get_position() );
}

void t_army::touch_armies( t_army*				 army, 
						   t_adv_map_point const& point, 
						   t_direction			 direction, 
						   t_adventure_frame*	 frame, 
						   t_adv_map_point const& return_point )
{
	// check if this is an empty boat
	if (empty() && is_boat()) 
	{
		if (army->is_boat())
		{
			// If the trigger is already in a boat, flag this one then continue to "trade"
			set_owner( army->get_owner_number() );
			update_state();
		}
		else 
		{
			// If the triggerer is not already in a boat, just have him appear to
			// board us by turning him into a boat and self destructing.
			t_level_map_point_2d	position	= get_position();
			t_town_type				boat_type	= m_boat_type;

			destroy();

			army->move( position );
			army->m_boat_type = boat_type;
			army->expend_embarkation_movement();
			army->update_state();
			frame->reset_pathfinder();
			frame->refresh_path();
			army->update_frame();
			army->trigger_events();
			return;
		}
	}

	if ( !same_team( army->get_owner(), get_owner() ) )
	{
		// Combat...
		if (m_is_graveyard)
			return;

		execute_script(k_army_scriptable_begin_combat, army);
		if (get_map()->is_game_over()) 
			return;
		army->execute_script(k_army_scriptable_begin_combat, this);
		if (get_map()->is_game_over()) 
			return;

		// change army to attack image
		if (army->has_action( k_adv_actor_action_attack ))
		{
			army->set_action( k_adv_actor_action_attack );
		}

		int angle;

		army->set_in_combat( true );
		angle = get_angle( get_position(), army->get_position() );
		set_direction( ::get_direction( angle ));
		set_in_combat( true );
		redraw_windows();

		// Before we fight, see what diplomacy and charm will accomplish
		bool we_ran = false;
		bool quick_combat = use_quick_combat();

		do_charm( army, frame );
		frame->update_army( army );
		frame->update_army( this );

		if ( !quick_combat && get_owner() == 0 && army->is_human()
			&& army->ai_value() >= ai_value() * 5.0 )
		{
			t_counted_ptr<t_dialog_enemy_runs> dialog = new t_dialog_enemy_runs( frame );

			dialog->run_modal();
			we_ran = dialog->enemy_ran();
			quick_combat = dialog->use_quick_combat();
		}

		// Start the fight
		t_army_ptr				ref = this;
		t_combat_context_ptr	context;
		context = new t_combat_context_army( army, this, return_point );
		run_combat( *context, we_ran, quick_combat );
	} 
	else
	{ 
		// Trade...
		if (get_owner()->is_computer() && (get_owner() == army->get_owner()) )
		{
			// Let the AI re-arrange the army.
			bool is_target_stronger; 
			shuffle_armies( get_map()->get_ai(), get_creatures(), army->get_creatures(), is_target_stronger );
			return;
		}

		// check if the cheating b*st*rd is trying to cheese a quest gate
		if (!get_map()->is_open( get_position(), *this )
			|| !get_map()->is_open( army->get_position(), *army ))
		{
			static t_external_string const k_text_no_gate_cheating( "gate_present.army" );

			ok_dialog( k_text_no_gate_cheating, true );
			return;
		}

		// Let the player re-arrange things
		frame->run_army_dialog( this, army );
	}
}

void t_army::on_combat_end( t_army* army, t_combat_result result, 
						    t_creature_array* losses, t_adventure_frame* frame )
{
	// change army to move image
	t_army_ptr ref = this;
	t_window_ptr frame_ref = frame;

	// change army to move image
	army->set_action( k_adv_actor_action_wait );
	frame->reset_pathfinder();

	// Update or destroy the armies as appropriate.
	// We have to special case this here because we KNOW we just came out of combat.
	// In the adventure frame, it leaves empty boats in place because in peaceful
	// conditions that is the right thing to do.
	if (army->is_boat() && army->get_creatures().empty()) {
		frame->destroy_army( army );
	} else {
		frame->update_army( army );
	}
	if (is_boat() && get_creatures().empty()) {
		frame->destroy_army( this );
	} else {
		frame->update_army( this );
	}


	if ( attacker_lost( result ) )
	{
		if ( m_map && army->get_owner_number() < 0 )
		{
			m_map->add_respawn_point( army->get_respawn_data() );
		}
	}

	if ( defender_lost( result ) )
	{
		if ( m_map && get_owner_number() < 0 )
		{
			m_map->add_respawn_point( get_respawn_data() );
		}
	}

	if (result == k_result_both_lost) 
	{
		if( !m_map->is_game_over() )
			execute_script(k_army_scriptable_lose_combat, army);
		if( !m_map->is_game_over() )
			army->execute_script(k_army_scriptable_lose_combat, this);
	} 
	else if (attacker_lost( result )) 
	{
		if( !m_map->is_game_over() )
			execute_script(k_army_scriptable_win_combat, army);
		if( !m_map->is_game_over() )
			army->execute_script(k_army_scriptable_lose_combat, this);
	} 
	else 
	{
		if( !m_map->is_game_over() )
			execute_script(k_army_scriptable_lose_combat, army);
		if( !m_map->is_game_over() )
			army->execute_script(k_army_scriptable_win_combat, this);
	}

	if (m_map != NULL)
		m_map->get_ai().reset_danger();
}

void t_army::set_in_combat( bool arg )
{
	if (m_in_combat == arg)
		return;
	on_move_begin();
	m_in_combat = arg;
	on_move_end();
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// get cost of moving into next square
// ---------------------------------------------------------------
int t_army::get_next_step_cost() const
{
	if (m_path.empty())
		return 0;
	return m_path.back().move_cost - m_path_start_cost;
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// expend some movement points
// ---------------------------------------------------------------
void t_army::update_frame()
{
	t_adventure_frame* frame = get_adventure_frame();

	if (frame->get_selected_army() == this)
	{
		frame->update_armies();
		frame->update_army();
	}
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// get the owning player (if any)
// ---------------------------------------------------------------
int t_army::get_owner_number() const
{
	return m_owner;
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// Color of owning player. Can be called before or after initialization
// ---------------------------------------------------------------
t_player_color t_army::get_owner_color() const
{
	t_player * owner = get_owner();

	if ( owner )
	{
		return owner->get_color();
	}
	else
	{
		return m_player_color;
	}
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// ---------------------------------------------------------------
t_player_color t_army::get_player_color() const
{
	return get_owner_color();
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// ---------------------------------------------------------------
int t_army::get_version() const
{
	return k_current_save_format_version;
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// write to save game
// ---------------------------------------------------------------
bool t_army::write_object( std::streambuf& stream ) const
{
	t_actor::write_object( stream );

	put<t_int8>( stream, m_owner );
	put<t_int8>( stream, m_boat_type );
	t_creature_array::write( stream );
	::write( stream, &m_path_destination, sizeof( m_path_destination ));

	put< t_uint16 >( stream, t_abstract_script_action::get_version() );
	if (	!write_built_in_events( stream )
		||	!write_events( stream, m_timed_events )
		||	!write_events( stream, m_triggerable_events )
		||	!write_events( stream, m_continuous_events ) )
		return false;

	put< t_int8 >( stream, m_initial_alignment );
	put< int >( stream, m_initial_growing_experience_value );
	put< int >( stream, m_initial_max_growth_per_day );
	put< int >( stream, m_initial_non_growing_experience_value );
	put< t_int8 >( stream, m_ai_wander_direction );
	put< t_uint8 >( stream, m_ai_importance );

	return true;
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// read from save game
// ---------------------------------------------------------------
bool t_army::read( std::streambuf& stream, int version )
{
	if ( !t_actor::read( stream, version ) )
		return false;

	m_player_color = k_player_gray;
	m_owner = get<t_int8>( stream );
	if (version < 2)
		m_boat_type = k_town_none;
	else
		m_boat_type = t_town_type( get<t_int8>( stream ) );

	if (version < 5)
	{
		if (!read_version( stream, 0 ))
			return false;
	} 
	else if (version < 9)
	{
		if (!read_version( stream, 1 ))
			return false;
	}
	else if (!t_creature_array::read( stream )) // version 9+ has a seperate version in creature array
		return false;

	if (version >= 3)
		::read( stream, &m_path_destination, sizeof( m_path_destination ));
	else
	{
		t_level_map_point_2d point;
		
		::read( stream, &point, sizeof( point ));
		m_path_destination = t_adv_map_point( point, false );
	}
	
	if ( version >= 4 )
	{
		int script_version = get< t_uint16 >( stream );
		if (	!read_built_in_events( stream, version, script_version )
			||	!read_events( stream, version, script_version, m_timed_events )
			||	!read_events( stream, version, script_version, m_triggerable_events )
			||	!read_events( stream, version, script_version, m_continuous_events ) )
			return false;
	}

	if ( version >= 5 )
	{
		m_initial_alignment = t_town_type( get< t_int8 >( stream ) );
		m_initial_growing_experience_value = get< int >( stream );
		m_initial_max_growth_per_day = get< int >( stream );
		m_initial_non_growing_experience_value = get< int >( stream );
	}
	else
	{
		compute_initial_alignment_and_xp();
	}

	if ( version >= 6 )
	{
		m_ai_wander_direction = get<t_int8>( stream );
	}
	
	if ( version < 8 )
	{
		m_ai_importance = k_ai_importance_normal;
	}
	else
	{
		m_ai_importance = t_ai_importance( get< t_uint8 >( stream ) );
	}

	m_trigger_events_position = m_location;

	return true;
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// ---------------------------------------------------------------
void t_army::take_events( t_events & new_events )
{
	std::swap_ranges(
		new_events.m_built_in_events,
		new_events.m_built_in_events + k_built_in_event_count,
		m_built_in_events );

	m_continuous_events.swap( new_events.m_continuous_events );
	m_timed_events.swap( new_events.m_timed_events );
	m_triggerable_events.swap( new_events.m_triggerable_events );
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// read from map file
// ---------------------------------------------------------------
bool t_army::read_from_map( std::streambuf& buffer, t_progress_handler* handler )
{
	int version = get< t_uint16 >( buffer );
	if ( version == 0 )
		return true;

	if ( version < 0 || version > k_current_map_format_version )
		return false;

	if ( version >= 2 )
	{
		m_player_color = t_player_color( get< t_uint8 >( buffer ) );
		if ( m_player_color < 0 || m_player_color >= k_player_color_count )
			return false;
	}
	else
		m_player_color = k_player_gray;

	m_owner = -1;

	if ( version >= 3 )
	{
		if ( !t_creature_array::read_from_map( buffer ) )
			return false;
	}
	else
	{
		bool summary_creatures = get< t_uint8 >( buffer ) != 0;
		bool read_result;
		if ( summary_creatures )
			read_result = t_creature_array::read_summary_from_map( buffer );
		else
			read_result = t_creature_array::read_from_map( buffer );
		if ( !read_result )
			return false;
	}

	if ( version >= 4 )
	{
		if ( version < 5 || get< t_int8 >( buffer ) != 0 )
		{
			set_patrol_type( static_cast< t_patrol_type >( get< t_int8 >( buffer ) + k_patrol_guard) ); // patrol type, 0=guard, 1=wander
			set_patrol_radius( get< t_int8 >( buffer ) ); // patrol radius, -1=unlimited
			if (get_patrol_radius() < 0)
				set_patrol_type( k_patrol_none );
			// force patrol radius to default for Guard
			if (get_patrol_type() == k_patrol_guard)
				set_patrol_radius( k_guard_maximum_radius );

		} else {
			if (m_player_color == k_player_gray) 
			{
				set_patrol_type( k_patrol_guard );
				set_patrol_radius( k_guard_maximum_radius );
			}
			else
			{
				set_patrol_type( k_patrol_none );
				set_patrol_radius( -1 );
			}
		}
	}

	if ( version >= 6 )
	{
		t_events new_events;
		if ( !new_events.read_from_map( buffer, 0 ) )
			return false;
		take_events( new_events );
	}

	if ( version >= 7 )
	{
		m_boat_type = t_town_type( get< t_int8 >( buffer ) );
		if (	m_boat_type != k_town_none
			&&	( m_boat_type < 0 || m_boat_type >= k_town_type_count ) )
			return false;
	}
	else
		m_boat_type = k_town_none;

	if ( version < 8 )
	{
		m_ai_importance = k_ai_importance_normal;
	}
	else
	{
		m_ai_importance = t_ai_importance( get< t_uint8 >( buffer ) );
	}

	// Transfer the data down to the creature array.
	set_importance( m_ai_importance );

	if ( version < 9 )
	{
		m_add_starting_troops = false;
	}
	else
	{
		m_add_starting_troops = ( get< t_uint8 >( buffer ) != 0 );
	}

	m_trigger_events_position = m_location;

	return true;
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// place on map
// ---------------------------------------------------------------
void t_army::place( t_adventure_map& map, t_adv_map_point const& point )
{
	t_actor::place( map, point );
	map.add( this );

	t_player * owner = get_owner();
	if ( owner != 0 )
	{
		add_to_owner_object_list();

		if ( m_is_graveyard )
			add_to_owner_graveyard_list();
		else
			add_to_owner_army_list();

		t_float_object floater( this );
		set_flag_color( owner->get_color() );
	}
}


// ---------------------------------------------------------------
// army which appears on the adventure map
// destroy object
// ---------------------------------------------------------------
void t_army::destroy()
{
	if (is_on_map())
	{
		remove_from_owner_graveyard_list();
		remove_from_owner_army_list();
		remove_from_owner_object_list();
		if (m_map != 0)
			m_map->remove( this );
	}
	clear();
	t_actor::destroy();
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// preplacement initialization
// ---------------------------------------------------------------
bool t_army::preplacement( t_adventure_map& map, int pass )
{
	// At this point the owner number has not been set, so use the player color
	if (!map.guards_can_move() && get_patrol_type() == k_patrol_guard)
		set_patrol_radius( 1 );
	// add starting troops - if requested.
	t_player* player = map.get_player( m_player_color );

	if (m_add_starting_troops && pass == 0 )
	{
		t_town_type alignment = k_town_none;

		if (player != 0)
			alignment = player->get_alignment();
		else if (!empty())
			alignment = get_leader().get_alignment();
		else
			alignment = m_boat_type;
		if (alignment != k_town_none)
		{
			add_start_creature( *this, alignment, k_town_dwelling_1 );
			add_start_creature( *this, alignment, k_town_dwelling_2 );
		}
	}

	return t_creature_array::preplacement( map, pass, player );
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// ---------------------------------------------------------------
void t_army::initialize( t_adventure_map& map )
{
	t_actor::initialize( map );

	t_float_object floater( this );

	if ( m_owner < 0 && m_player_color != k_player_gray )
	{
		m_owner = map.get_or_add_player_number( m_player_color );

		// m_player_color is only used for initialization
		m_player_color = k_player_gray;

		t_player * owner = get_owner();

		add_to_owner_lists();
		set_flag_color( owner->get_color() );

		on_owner_changed( m_owner, -1 );
	}

	if (random(2) == 0)
		set_direction( k_direction_southeast );
	else
		set_direction( k_direction_southwest );

	// If initially placed on a ramp, place on top of the ramp
	if ( map[get_position()].has_ramp() )
	{
		t_adv_map_point position =  get_position();
		position.on_bridge = true;
		t_actor::move( position ); 
	}

	m_initial_location = get_position();
	
	if ( m_initial_growing_experience_value == -1 )
		compute_initial_alignment_and_xp();

	enable_highlight( !empty() && m_owner < 0 );
	
	if (m_map != NULL)
		m_map->cache_adventure_object_state( this );
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// ---------------------------------------------------------------
void t_army::set_owner( int arg )
{
	if ( arg == m_owner )
		 return;

	if ( get_map() != 0 )
	{
		remove_from_owner_lists();

		int old_owner = m_owner;
		m_owner = arg;

		t_player_color new_flag_color;

		t_player * owner = get_owner();

		if ( owner != 0 )
			new_flag_color = owner->get_color();
		else
			new_flag_color = k_player_gray;

		add_to_owner_lists();

		{
			t_float_object floater( this );
			set_flag_color( new_flag_color );
			enable_highlight( !empty() && owner == 0 );
		}

		on_owner_changed( m_owner, old_owner );

		process_timed_events( *get_map(), false );
	}
	else
		m_owner = arg;
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// ---------------------------------------------------------------
bool t_army::subimage_is_underlay( int subimage_num ) const
{
	// Hack: avoid graveyards disappearing on bridges by making them not underlays
	// when on a bridge
	return m_is_graveyard && !m_location.on_bridge;
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// return whether another army should be blocked by this one
// ---------------------------------------------------------------
bool t_army::blocks_army( t_creature_array const& army, t_path_search_type path_type ) const
{
	// armys don't block themselves.  Graveyards don't block anything.
	// graveyards aren't blocked by armies, either (only really comes up
	// when checking if someone's trying to cheese a quest gate with a graveyard
	// in it).
	if ((&army == this) || m_is_graveyard || army.is_graveyard())
		return false;

	if ( path_type != k_path_search_standard )
	{
		// Nearby space doesn't care about armies
		// Caravans go through friendly armies, and hostile
		// armies are handled by special code.
		if (    path_type == k_path_search_find_nearby_space
			 || path_type == k_path_search_caravan 
			 || path_type == k_path_search_ai_value
			 || path_type == k_path_search_ai_danger )
			return false;

		// Neutral turn pathing, don't path through armies.
		if (   path_type == k_path_search_ai_neutral_army 
			|| path_type == k_path_search_ai_guarding_army
			|| path_type == k_path_search_enemy_activation
			|| path_type == k_path_search_place_army
			|| path_type == k_path_search_move_army )
			 return true;

		if (is_boat() && empty() && !army.is_boat())
			return false;

		return same_team( army.get_owner(), get_owner() );
	}
	
	int team;

	if (army.get_owner_number() < 0)
	{
		team = -1;
	}
	else
	{
		t_player * player = army.get_owner();

		if ( player == NULL ) 
		{
			// Army not yet placed on map
			int player_number = army.get_owner_number();
			player = &get_map()->get_player( player_number );
		}

		team = player->get_team();
	}

	return is_visible_to( team );
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// ---------------------------------------------------------------
t_footprint const& t_army::get_footprint() const
{
	if (m_is_graveyard)
	{
		static t_graveyard_footprint const k_footprint;

		return k_footprint;
	}
	return get_model();
}

// ---------------------------------------------------------------
// army which appears on the adventure map
// ---------------------------------------------------------------
bool t_army::is_removable() const
{
	return true;
}

// ---------------------------------------------------------------
// ---------------------------------------------------------------
bool t_army::process_timed_events( t_adventure_map& map, bool start_of_day )
{
	bool result = false;

	int i;
	int size = m_timed_events.size();

	for (i = 0; i < size; i++) {
		t_timed_event_ptr& event = m_timed_events[i];
		if ( event->is_active_on_day(map.get_day()) 
			&& (&map.get_current_player() == get_owner())
			&& event->ownership_test(get_owner())
			&& (start_of_day || !event->has_executed()) )
		{
			result = true;

			event->set_execution_flag();
			event->execute_effects(map.get_current_player(), get_adventure_frame());
			get_adventure_frame()->update();

			t_timed_event::t_script const & script = event->get_script();
			script.execute(t_script_context_army(&map, this, get_owner(), NULL, NULL, &get_position()));
			if( map.is_game_over() )
				return false;

			get_adventure_frame()->update();
			post_execute_validate(this);

			if (script.pending_removal()) {
				script.clear_removal();
				event = new t_ownable_timed_event;
			}
		}
		else
			if (start_of_day)
				event->clear_execution_flag();
	}

	for (i = 0; i < t_creature_array::k_size; i++) {
		t_hero* hero = (*this)[i].get_hero();
		if (hero && hero->process_timed_events(map, this, get_owner(), &get_position(), start_of_day) ) {
			get_adventure_frame()->update();
			post_execute_validate(this);
			result = true;
		}
	}

	return result;
}

// -----------------------------------------------------------
// -----------------------------------------------------------
bool t_army::process_continuous_events( t_adventure_map& map )
{
	bool result = false;

	int i;
	int size = m_continuous_events.size();

	for (i = 0; i < size; i++) {
		t_continuous_event_ptr & event = m_continuous_events[i];
		if (( !event->get_run_only_during_owners_turn() || &map.get_current_player() == get_owner() )
			&& event->ownership_test(get_owner()) )
		{
			result = true;

			t_continuous_event::t_script const & script = event->get_script();
			script.execute(t_script_context_army(&map, &get_creatures(), get_owner(), NULL, NULL, &get_position()));
			if( map.is_game_over() )
				return false;
			get_adventure_frame()->update();
			post_execute_validate(this);

			if (script.pending_removal()) {
				script.clear_removal();
				event = new t_ownable_continuous_event;
			}
		}
	}

	for (i = 0; i < t_creature_array::k_size; i++) {
		t_hero* hero = (*this)[i].get_hero();
		if (hero && hero->process_continuous_events(map, &get_creatures(), get_owner(), &get_position()) ) {
			get_adventure_frame()->update_army(this);
			result = true;
		}
	}

	return result;
}

// -----------------------------------------------------------
// -----------------------------------------------------------
bool t_army::process_triggerable_events( t_adventure_map& map, std::string const& name )
{
	bool result = false;

	int size = m_triggerable_events.size();
	for (int i = 0; i < size; i++) {
		t_triggerable_event_ptr & event = m_triggerable_events[i];
		if (( string_insensitive_compare(event->get_name(), name) == 0 )
			&& event->ownership_test(get_owner()) )
		{
			result = true;

			event->execute_effects(map.get_current_player(), get_adventure_frame());
			get_adventure_frame()->update();
			
			t_triggerable_event::t_script const & script = event->get_script();
			script.execute(t_script_context_army(&map, this, get_owner(), NULL, NULL, &get_position()));
			if( map.is_game_over() )
				return false;

			get_adventure_frame()->update();
			post_execute_validate(this);

			if (script.pending_removal()) {
				script.clear_removal();
				event = new t_ownable_triggerable_event;
			}
		}
	}

	for (int i = 0; i < t_creature_array::k_size; i++) {
		t_hero* hero = (*this)[i].get_hero();
		if (hero && hero->process_triggerable_events(map, name, this, get_owner(), &get_position()) ) {
			get_adventure_frame()->update_army(this);
			result = true;
		}
	}

	return result;
}


// ---------------------------------------------------------------
// ---------------------------------------------------------------
int t_army::get_subimage_depth_offset( int subimage_num ) const
{
	int result = t_actor::get_subimage_depth_offset( subimage_num );

	// cheesy hack: reduce depth by one if army is on a bridge, to force
	// it to draw in front of the bridge.
	if (m_location.on_bridge)
		--result;
	return result;
}

// --------------------------------------------------------
// --------------------------------------------------------
int t_army::get_scouting_range() const
{
	return m_scouting_range;
}

// --------------------------------------------------------
// --------------------------------------------------------
int t_army::compute_scouting_range() const
{
	int creature_range = t_creature_array::compute_scouting_range();
	// Boats will always have at least a range of 3
	int const k_boat_range = 3;
	if ( !is_boat() || creature_range > k_boat_range )
		return creature_range;
	return k_boat_range;
}

// --------------------------------------------------------
// --------------------------------------------------------
void t_army::update_scouting_range()
{
	int new_scouting_range = compute_scouting_range();
	if ( new_scouting_range == m_scouting_range )
		return;

	int old_scouting_range = m_scouting_range;
	m_scouting_range = new_scouting_range;

	on_scouting_range_changed( new_scouting_range, old_scouting_range );
}

// ---------------------------------------------------------------
// check if army triggers this army
// ---------------------------------------------------------------
bool t_army::is_triggered_by( t_creature_array const& army ) const
{
	// armies cannot trigger themselves
	if (&army == this)
		return false;
	// armies can only trigger graveyards if they belong to the same player
	if (m_is_graveyard)
		return army.get_owner_number() == get_owner_number();
	// enemies always trigger.
	if (!same_team( get_owner(), army.get_owner() ))
		return true;
	// check if there's a quest guard in this tile.
	if (!get_map()->is_open( get_position(), *this ))
		return false; // no cheesing of quest guards by trading with armies on them!
	return true;
}

// ---------------------------------------------------------------
// ---------------------------------------------------------------
void t_army::read_postplacement( t_adventure_map& map )
{
	t_actor::read_postplacement( map );

	t_creature_array::read_postplacement( map );
}

// ---------------------------------------------------------------
// ---------------------------------------------------------------
bool t_army::read_built_in_events(
	std::streambuf &	stream,
	int					version,
	int					script_version )
{
	assert( version >= 4 );

	t_built_in_event_id event_id;
	for (	event_id = t_built_in_event_id( 0 );
			event_id < k_built_in_event_count;
			enum_incr( event_id ) )
	{
		t_built_in_event_ptr new_event_ptr( new t_built_in_event );
		if ( !new_event_ptr->read( stream, script_version ) )
			return false;
		m_built_in_events[ event_id ] = new_event_ptr;
	}

	return true;
}

// ---------------------------------------------------------------
// ---------------------------------------------------------------
bool t_army::write_built_in_events( std::streambuf & stream ) const
{
	t_built_in_event_id event_id;
	for (	event_id = t_built_in_event_id( 0 );
			event_id < k_built_in_event_count;
			enum_incr( event_id ) )
	{
		if ( !m_built_in_events[ event_id ]->write( stream ) )
			return false;
	}

	return true;
}

// ---------------------------------------------------------------
// ---------------------------------------------------------------
void t_army::execute_script( t_army_scriptable_event event, t_army* opposing_army)
{
	assert( event >= 0 && event < k_built_in_event_count );
	assert( opposing_army != 0 );

	t_built_in_event_ptr & event_ptr = m_built_in_events[ event ];

	if (!event_ptr->ownership_test(get_owner())) return;

	t_counted_ptr<t_adventure_frame> frame = get_adventure_frame();
	
	event_ptr->execute_effects(get_map()->get_current_player(), get_adventure_frame());
	frame->update();

	t_built_in_event::t_script const & script = event_ptr->get_script();
	script.execute( t_script_context_army( get_map(), &get_creatures(), get_owner(), &opposing_army->get_creatures(), opposing_army->get_owner(), &get_position() ) );
	if( get_map()->is_game_over() )
		return;

	frame->update();
	post_execute_validate(this);
	post_execute_validate(opposing_army);
		
	if ( script.pending_removal() ) {
		script.clear_removal();
		event_ptr = new t_built_in_event;
	}

	get_map()->process_continuous_events( frame );
	frame->update();
}

// ---------------------------------------------------------------
// ---------------------------------------------------------------
bool t_army::is_boat() const
{
	return m_boat_type != k_town_none;
}

void t_army::expend_all_movement()
{
	t_creature_array::expend_all_movement();
	update_frame();
}

// ---------------------------------------------------------------
// ---------------------------------------------------------------
void t_army::expend_most_movement( int max_remaining_movement )
{
	t_creature_array::expend_most_movement( max_remaining_movement );
	update_frame();
}

// ---------------------------------------------------------------
// ---------------------------------------------------------------
void t_army::change_movement( int amount )
{
	t_creature_array::change_movement( amount );
	update_frame();
}

// ---------------------------------------------------------------
// Expend motion as appropriate for boarding (or leaving) a boat
// ---------------------------------------------------------------
void t_army::expend_embarkation_movement()
{
	if (!has_seamans_hat())
		expend_all_movement();
}

// ---------------------------------------------------------------
// Return the respawn point that matches this army.
// ---------------------------------------------------------------
t_respawn_point t_army::get_respawn_data() const
{
	return t_respawn_point( m_initial_alignment,
					        m_initial_growing_experience_value,
							m_initial_max_growth_per_day,
						    m_initial_non_growing_experience_value,
							m_map && m_map->is_ocean( m_initial_location ),
							m_patrol_radius,
							m_patrol_type,
							m_initial_location );
}


// ---------------------------------------------------------------
// Set the initial_... fields from the current set of creatures
// in the creature array
// ---------------------------------------------------------------
void t_army::compute_initial_alignment_and_xp()
{
	int xp_by_alignment[ k_town_type_count ];

	int i;
	for ( i = 0; i < ELEMENTS_OF( xp_by_alignment ); i++ )
	{
		xp_by_alignment[i] = 0;
	}

	m_initial_growing_experience_value = 0;
	m_initial_non_growing_experience_value = 0;
	m_initial_max_growth_per_day = 0;

	for ( i = 0; i < t_creature_array::k_size; i++ )
	{
		t_creature_stack const & creature_stack = (*this)[i];

		xp_by_alignment[ creature_stack.get_alignment() ] += creature_stack.get_experience_value();

		if ( creature_stack.get_hero() )
		{
			// Heroes don't grow
			m_initial_non_growing_experience_value += creature_stack.get_experience_value();
		}
		else
		{
			t_creature const * creature = creature_stack.get_creature();

			if ( creature )
			{
				m_initial_growing_experience_value += creature->get_experience_value();

				t_creature_traits const & traits = get_traits( creature->get_creature_type() );

				m_initial_max_growth_per_day += traits.weekly_growth * traits.experience / 7;
			}
		}
	}

	// Alignment is alignment with most XP in it.
	int most_xp = -1;

	for ( i = 0; i < ELEMENTS_OF( xp_by_alignment ); i++ )
	{
		if ( xp_by_alignment[i] > most_xp )
		{
			most_xp = xp_by_alignment[i];
			m_initial_alignment = t_town_type(i);
		}
	}
}

// ------------------------------------------------------------
// ------------------------------------------------------------
t_army::t_events::t_events()
{
	std::fill(
		m_built_in_events,
		m_built_in_events + k_built_in_event_count,
		t_built_in_event_ptr( new t_built_in_event ) );
}

// ------------------------------------------------------------
// ------------------------------------------------------------
bool t_army::t_events::read_from_map(
	std::streambuf &	stream,
	int					version )
{
	return		read_built_in_events_from_map( stream, version )
			&&	read_events_from_map( stream, version, m_timed_events )
			&&	read_events_from_map( stream, version, m_triggerable_events )
			&&	read_events_from_map( stream, version, m_continuous_events );
}

// ---------------------------------------------------------------
// ---------------------------------------------------------------
bool t_army::t_events::read_built_in_events_from_map(
	std::streambuf &	stream,
	int					version )
{
	t_built_in_event_id event_id;
	for (	event_id = t_built_in_event_id( 0 );
			event_id < k_built_in_event_count;
			enum_incr( event_id ) )
	{
		t_built_in_event_ptr new_event_ptr( new t_built_in_event );
		if ( !new_event_ptr->read_from_map( stream ) )
			return false;
		m_built_in_events[ event_id ] = new_event_ptr;
	}

	return true;
}

// ---------------------------------------------------------------
// ---------------------------------------------------------------
bool t_army::is_visible_to( int team_num ) const
{
	// Empty boats are always visible under the fog of war
	if ( is_boat() && empty() )
		return true;
	if (!get_enable_shroud())
		return true;
	
	t_player const * owner = get_owner();

	if ( owner != 0 && owner->get_team() == team_num)
		return true;

	t_adventure_tile const& tile = (*get_map())[get_position()];

	if (tile.get_visibility( team_num ) != k_tile_visible)
		return false;

	if (m_in_combat)
		return true;

	return get_stealth_level() <= tile.get_anti_stealth( team_num );
}

bool t_army::can_be_hidden() const
{
	return true;
}

// ---------------------------------------------------------------
// ---------------------------------------------------------------
int	t_army::ai_get_wander_direction() const
{
	return m_ai_wander_direction;
}

// ---------------------------------------------------------------
// ---------------------------------------------------------------
void t_army::ai_set_wander_direction(int direction)
{
	m_ai_wander_direction = direction;
}

// ---------------------------------------------------------------
// ---------------------------------------------------------------
float t_army::ai_value( t_adventure_ai const& ai, t_creature_array const& army, int move_cost ) const
{
	if (army.get_owner() == get_owner())
	{
		if (is_graveyard())
		{
			if (!army.can_add_hero() && (army.get_hero_count() != 0) )
				return 0.0f;

			float value_of_hero = ai_value_including_dead() * 3;
			value_of_hero += 2500 * get_owner()->get_material_value(k_gold); // Approx gold value of a hero just as an added insentive.
			return value_of_hero;
		}
		else
		{
			float value_target = get_creatures().ai_value();
			float value_source = army.ai_value();
			
			if (value_target == 0 || value_source == 0)
				return 0.0f;

			float shuffle_value = ai.get_cache().value_of_creature_swap( ai, *this, army );

			if (shuffle_value == 0.0f)
				return 0.0f;

			float value_of_larger = std::max( value_target, value_source );

			float comparison_ratio = shuffle_value / value_of_larger;
			
			if ((move_cost > 500) || (comparison_ratio < 0.20f))
			{
				if (ai.moving_last_army())
					return shuffle_value * 0.05f;
				else
					return 0.0f;
			}
			else
				return shuffle_value;
		}
	}
	else
	{
		t_adventure_map const&	map = *get_map();
		t_adventure_tile const& tile = map[get_position()];
		int						team;

		if (army.get_owner() == 0)
			team = -1; // valid for the scouting test
		else
			team = army.get_owner()->get_team();

		if (get_stealth_level() > tile.get_anti_stealth( team ))
			return 0.0f;

		float scale_for_aggression 
			= ai.scale_for_combat_aggression( army.get_owner(), get_owner() );
		if (scale_for_aggression == 0.0f)
			return 0.0f;
		
		return scale_for_aggression * value_of_combat( &army, &get_creatures() ) 
			+ m_ai_data_cache->get_bounty();
	}
}

// ---------------------------------------------------------------
// ---------------------------------------------------------------
void t_army::on_begin_turn()
{
	t_creature_array::on_begin_turn();
	t_actor::on_begin_turn();
}

// ---------------------------------------------------------------
// ---------------------------------------------------------------
void t_army::on_end_turn()
{
	t_creature_array::on_end_turn();
	t_actor::on_end_turn();
}

// ---------------------------------------------------------------
// ---------------------------------------------------------------
t_army::t_icon_type t_army::get_icon_type() const
{
	return !empty() ? k_adv_object_icon_army : k_adv_object_icon_none;
}

// ---------------------------------------------------------------
// ---------------------------------------------------------------
int t_army::get_attack_range() const
{
	return k_army_attack_radius;
}

// ---------------------------------------------------------------
// ---------------------------------------------------------------
t_skill_mastery t_army::get_anti_stealth_level() const
{
	return t_creature_array::get_anti_stealth_level();
}


// ------------------------------------------------------------------------
// Trigger all the placed events at the army's current location 
// ------------------------------------------------------------------------
void t_army::trigger_events()
{
	t_army_ptr ref = this; 

	if ( !is_on_map() || empty() )
		return;

	// If we have already triggered events for our current location,
	// don't do it twice. Insist on a move before triggering stuff
	// again.
	if ( m_trigger_events_position == m_location )
		return;

	t_counted_ptr<t_adventure_map> map = get_map();
	t_adv_map_point  triggered_location = m_location;
	t_adventure_tile const& tile = map->get_adv_tile( triggered_location );

	m_trigger_events_position = m_location;

	if (tile.is_trigger( triggered_location.on_bridge ))
	{
		// Save list of current adventure objects to avoid headaches if some 
		// are deleted or created during triggers
		std::vector<t_adventure_object_ptr> triggers;
		const std::vector<int>& tile_triggers = tile.get_triggers(triggered_location.on_bridge);
		for (std::vector<int>::const_iterator index = tile_triggers.begin(); index != tile_triggers.end(); index++)
		{
			triggers.push_back(t_adventure_object_ptr(&map->get_adv_object(*index)));
		}

		bool triggered = false;
		std::vector<t_adventure_object_ptr>::iterator
			trigger_index = triggers.begin(),
			trigger_end = triggers.end();
		
		while( (trigger_index != trigger_end) && !map->is_game_over() )
		{
			if ((*trigger_index++)->trigger_event(*this))
				triggered = true;

			if ( map->is_game_over() )
				return;

			if ( !is_on_map() || triggered_location != m_location )
				break; // We've moved; stop processing this location
		}

		if (!map->is_game_over() && triggered && get_adventure_frame() )
		{
			get_adventure_frame()->update();
		}
	}
}

// ------------------------------------------------------------
// trigger an event
// ------------------------------------------------------------
bool t_army::trigger_event(t_army& army)
{
	if (!m_is_graveyard)
		return false;

	t_player* player = army.get_owner();
	if ( player && player->is_computer() && player == get_owner())
	{
		bool is_target_stronger; 
		shuffle_armies( get_map()->get_ai(), army.get_creatures(), get_creatures(), is_target_stronger );
		return true;
	}
	return false;
}

// ------------------------------------------------------------
// select in adventure frame
// ------------------------------------------------------------
bool t_army::select()
{
	t_adventure_frame* frame = get_adventure_frame();

	if (frame == 0)
		return false;
	frame->select_army( this );
	return true;
}


// ------------------------------------------------------------
// footprint information for graveyard
// ------------------------------------------------------------
bool t_graveyard_footprint::are_any_cells_flat() const
{
	return false;
}

// ------------------------------------------------------------
// footprint information for graveyard
// ------------------------------------------------------------
bool t_graveyard_footprint::are_any_cells_impassable() const
{
	return false;
}

// ------------------------------------------------------------
// footprint information for graveyard
// ------------------------------------------------------------
t_map_point_2d t_graveyard_footprint::get_size() const
{
	return t_map_point_2d(1,1);
}

// ------------------------------------------------------------
// footprint information for graveyard
// ------------------------------------------------------------
bool t_graveyard_footprint::is_cell_flat( t_map_point_2d const & point ) const
{
	return false;
}

// ------------------------------------------------------------
// footprint information for graveyard
// ------------------------------------------------------------
bool t_graveyard_footprint::is_cell_impassable( t_map_point_2d const & point ) const
{
	return false;
}

// ------------------------------------------------------------
// footprint information for graveyard
// ------------------------------------------------------------
bool t_graveyard_footprint::is_left_edge_trigger( t_map_point_2d const & point ) const
{
	return true;
}

// ------------------------------------------------------------
// footprint information for graveyard
// ------------------------------------------------------------
bool t_graveyard_footprint::is_right_edge_trigger( t_map_point_2d const & point ) const
{
	return true;
}

// ------------------------------------------------------------
// footprint information for graveyard
// ------------------------------------------------------------
bool t_graveyard_footprint::is_trigger_cell( t_map_point_2d const& point ) const
{
	return true;
}

